package leetcode;

/**
 * Created with IntelliJ IDEA.
 * Description:110.平衡二叉树
 * User: 东莞呵呵
 * Date:2022-07-20
 * Time:15:08
 */
public class TestDemo4 {
    /*
    左右树深度差小于1，且左右树都是平衡二叉树
    时间复杂度：O（N^2）
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return (Math.abs(getHeight(root.left)-getHeight(root.right))<=1)&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        return (Math.max(getHeight(root.left),getHeight(root.right))+1);
    }
    /*
    时间复杂度是O(n)
     */
    public int getHeight2(TreeNode root){
        if(root==null){
            return 0;
        }else if(getHeight2(root.left)>=0&&getHeight2(root.right)>=0&& (Math.abs(getHeight2(root.left)-getHeight2(root.right))<=1)){
            return (Math.max(getHeight(root.left),getHeight(root.right))+1);
        }
        return -1;
    }
    public boolean isBalanced2(TreeNode root){
        if(root==null){
            return true;
        }
        return getHeight2(root)>=0;
    }
}
